LDPC (Low Density Parity Check) codes have high error correction capabilities, and are now beginning to be widely used in transmission systems including digital satellite broadcasting such as DVB (Digital Video Broadcasting)-S.2, which is implemented in Europe (see Non-Patent Document 1, for example). Also, the use of LDPC codes in next-generation digital terrestrial broadcasting is being considered.
Recent studies are making it clearer that LDPC codes having longer code lengths have capabilities closer to the Shannon limit, like turbo codes and the like. Also, an LDPC code is characterized in that the minimum distance is proportional to its code length. In view of this, advantageous features of an LDPC code include a preferable block error probability and almost no occurrences of a so-called error floor phenomenon, which are observed in decoding characteristics of turbo codes and the like.
In the following, such LDPC codes are described in detail. LDPC codes are linear codes, and are not necessarily binary codes. In this description, however, LDPC codes are described as binary codes.
The most significant feature of an LDPC code is that the parity check matrix defining the LDPC code is sparse. Here, a sparse matrix is a matrix that has a very small number of matrix elements “1” (a matrix in which most elements are “0”).
FIG. 1 shows an example of the parity check matrix H of an LDPC code.
In the parity check matrix H shown in FIG. 1, the weight in each column (the column weight) (the number of elements “1”) is “3”, and the weight in each row (the row weight) is “6”.
In encoding with the use of an LDPC code (LDPC encoding), a generator matrix G is generated based on the parity check matrix H, for example, and binary information bits are multiplied by the generator matrix G, to generate a code word (an LDPC code).
Specifically, an encoding device that performs LDPC encoding first calculates such a generator matrix G as to satisfy the equation, GHT=0, with respect to the transposed matrix HT of the parity check matrix H. Here, if the generator matrix G is a K×N matrix, the encoding device multiplies the generator matrix G by a bit string (a vector u) of information bits consisting of K bits, to generate a code word c (=uG) consisting of N bits. The code word (an LDPC code) generated by the encoding device is received by a receiving side via a predetermined channel.
Decoding of an LDPC code can be performed by using a message passing algorithm that is an algorithm suggested as Probabilistic Decoding by Gallager and is based on the belief propagation in a so-called Tanner graph formed with variable nodes (also referred to as message nodes) and check nodes. Hereinafter, the variable nodes and the check nodes will also be referred to simply as nodes, where appropriate.
FIG. 2 shows the procedures for decoding an LDPC code.
It should be noted that the real value (reception LLR) representing the log likelihood ratio indicating the likelihood that the value of the ith sign bit in an LDPC code (one code word) received on the receiving side is “0” will be also referred to as the received value u0i, where appropriate. Also, a message that is output from a check node is represented by uj, and a message that is output from a variable node is represented by vi.
First, in decoding of an LDPC code, as shown in FIG. 2, the LDPC code is received in step S11. A message (a check node message) uj is initialized to “0”, and a variable k that is an integer as a repetitive processing counter is initialized to “0”. The operation then moves on to step S12.
In step S12, based on the received value u0i obtained by receiving the LDPC code, the calculation shown in the equation (1) (a variable node calculation) is performed, to determine a message (a variable node message) vi. Further, based on the message vi, a calculation (a check node calculation) shown in the equation (2) is calculated, to determine a message uj.
                    [                  Mathematical          ⁢                                          ⁢          Formula          ⁢                                          ⁢          1                ]                                                                      v          i                =                              u                          0              ⁢                                                          ⁢              i                                +                                    ∑                              j                =                1                                                              d                  v                                -                1                                      ⁢                          u              j                                                          (        1        )                                [                  Mathematical          ⁢                                          ⁢          Formula          ⁢                                          ⁢          2                ]                                                                      tanh          ⁡                      (                                          u                j                            2                        )                          =                              ∏                          i              =              1                                                      d                c                            -              1                                ⁢                                          ⁢                      tanh            ⁡                          (                                                v                  i                                2                            )                                                          (        2        )            
In the equation (1) and the equation (2), dv, and dc represent parameters that can be arbitrarily selected and represent the numbers of elements “1” in the vertical direction (column) and the horizontal direction (row) in a parity check matrix H, respectively. In the case of a (3, 6) code, for example, dv is 3, and dc is 6.
In the variable node calculation shown in the equation (1) and the check node calculation shown in the equation (2), messages that are input from the edges (the lines each connecting a variable node and a check node) that are about to output messages are not subjected to the calculations. Therefore, the range of calculation is 1 to dv−1 or 1 to dc−1. In practice, the check node calculation shown in the equation (2) is performed by preparing beforehand a table of the function R (v1, v2) shown in the equation (3) defined by one output for the two inputs v1 and v2, and continuously (recursively) using the table as shown in the equation (4).
[Mathematical Formula 3]x=2 tan h−1{tan h(v1/2)tan h(v2/2)}=R(v1,v2)  (3)[Mathematical Formula 4]uj=R(v1,R(v2,R(v3 . . . R(vdo−2,vdc−1))))  (4)
Further, in step S12, the variable k is incremented only by “1”, and the operation then moves on to step S13. In step S13, a check is made to determine whether the variable k is larger than a predetermined number C of repetitions of decoding. If the variable k is determined not to be larger than C in step S13, the operation returns to step S12, and the same procedures as above are repeated.
If the variable k is determined to be larger than C in step S13, the operation moves on to step S14, and the calculation shown in the equation (5) is performed to determine the message vi as a decoding result to be output at last. The message vi is then output, and the LDPC code decoding operation comes to an end.
                    [                  Mathematical          ⁢                                          ⁢          Formula          ⁢                                          ⁢          5                ]                                                                      v          i                =                              u                          0              ⁢                                                          ⁢              i                                +                                    ∑                              j                =                1                                            d                v                                      ⁢                          u              j                                                          (        5        )            
Here, the calculation shown in the equation (5) is performed by using the messages uj from all the edges connected to the variable nodes, unlike the variable node calculation shown in the equation (1).
FIG. 3 shows an example of the parity check matrix H of a (3, 6) LDPC code (a code rate of 1/2, a code length of 12).
In the parity check matrix H shown in FIG. 3, the column weight is 3, and the row weight is 6, as in the case illustrated in FIG. 1.
FIG. 4 shows a Tanner graph of the parity check matrix H shown in FIG. 3.
In FIG. 4, each “+” represents a check node, and each “=” represents a variable node. The check nodes and the variable nodes correspond to the rows and the columns, respectively, of the parity check matrix H. The connecting lines between the check nodes and the variable nodes are the edges, and are equivalent to the elements “1” of the parity check matrix.
That is, when the element in the jth row and the ith column in the parity check matrix is 1, the variable node (represented by “=”) that is the ith from the top, and the check node (represented by “+”) that is the jth from the top are connected by an edge in FIG. 4. The edge indicates that the sign bit corresponding to the variable node has a constraint corresponding to the check node.
According to Sum Product Algorithm, which is a method of decoding LDPC codes, a variable node calculation and a check node calculation are repeatedly performed.
FIG. 5 shows a variable node calculation to be performed at a variable node.
At the variable node, the message vi corresponding to the edge to be calculated can be determined through a variable node calculation shown in the equation (1) using the messages u1 and u2 from the other edges connected to the variable node, and the received value u0i. The message corresponding to any of the other edges can be determined in the same manner as above.
FIG. 6 shows a check node calculation to be performed at a check node.
The check node calculation shown in the equation (2) can also be expressed by the equation (6) using the relationship expressed by the equation, a×b=exp{ln(|a|)+ln(|b|)}×sign(a)×sign(b). Here, sign (x) is 1 when x≧0, and is −1 when x<0.
                    [                  Mathematical          ⁢                                          ⁢          Formula          ⁢                                          ⁢          6                ]                                                                                                                u                j                            =                            ⁢                              2                ⁢                                                                  ⁢                                                      tanh                                          -                      1                                                        (                                                            ∏                                              i                        =                        1                                                                                              d                          c                                                -                        1                                                              ⁢                                                                                  ⁢                                          tanh                      ⁡                                              (                                                                              v                            i                                                    2                                                )                                                                              )                                                                                                        =                            ⁢                              2                ⁢                                                                  ⁢                                                      tanh                                          -                      1                                                        [                                      exp                    ⁢                                          {                                                                        ∏                                                      i                            =                            1                                                                                                              d                              c                                                        -                            1                                                                          ⁢                                                  ln                          ⁡                                                      (                                                                                                                        tanh                                ⁡                                                                  (                                                                                                            v                                      i                                                                        2                                                                    )                                                                                                                                                    )                                                                                              }                                        ×                                                                  ∏                                                  i                          =                          1                                                                                                      d                            c                                                    -                          1                                                                    ⁢                                              sign                        ⁡                                                  (                                                      tanh                            ⁡                                                          (                                                                                                v                                  i                                                                2                                                            )                                                                                )                                                                                                      ]                                                                                                        =                            ⁢                              2                ⁢                                                                  ⁢                                                      tanh                                          -                      1                                                        [                                      exp                    ⁢                                          {                                              -                                                  (                                                                                    ∏                                                              i                                =                                1                                                                                                                              d                                  c                                                                -                                1                                                                                      ⁢                                                          -                                                              ln                                ⁡                                                                  (                                                                      tanh                                    ⁡                                                                          (                                                                                                                                                                                                              v                                            i                                                                                                                                                                    2                                                                            )                                                                                                        )                                                                                                                                              )                                                                    }                                                        ]                                ×                                                      ∏                                          i                      =                      1                                                                                      d                        c                                            -                      1                                                        ⁢                                      sign                    (                                          v                      i                                        )                                                                                                          (        6        )            
When x≧0, the equation, φ−1(x)=2 tan h−1(e−x), is satisfied where the function φ(x) is defined as φ(x)=ln(tan h(x/2)). Accordingly, the equation (6) can be transformed into the equation (7).
                    [                  Mathematical          ⁢                                          ⁢          Formula          ⁢                                          ⁢          7                ]                                                                      u          j                =                                            ϕ                              -                1                                      (                                          ∑                                  i                  =                  1                                                                      d                    c                                    -                  1                                            ⁢                              ϕ                ⁡                                  (                                                                                v                      i                                                                            )                                                      )                    ×                                    ∏                              i                =                1                                                              d                  c                                -                1                                      ⁢                          sign              (                              v                i                            )                                                          (        7        )            
At the check node, the check node calculation shown in the equation (2) is performed according to the equation (7).
That is, at the check node, the message uj corresponding to the edge to be calculated can be determined through the check node calculation shown in the equation (7) using the messages v1, v2, v3, v4, and v5 from the other edges connected to the check node, as shown in FIG. 6. The message corresponding to any of the other edges can be determined in the same manner as above.
It should be noted that the function φ(x) in the equation (7) can be expressed by the equation, φ(x)=ln((ex+1)/(ex−1)), and φ(x)=φ−1(x) is satisfied when x>0. When the function φ(x) and φ−1(x) are implemented in hardware, LUTs (Look Up Tables) may be used, but both tables are identical LUTs.